package com.sx.sx1.lintcode.day717;

public class LK394_LC575 {

    static class Solution {
        /**
         * @param s: an expression includes numbers, letters and brackets
         * @return: a string
         */
        public String expressionExpand(String s) {
            //和基础计算器的题目类似
            return f(s, 0).data;
        }

        public Info f(String s, int idx) {
            int cur = 0;
            StringBuilder sb = new StringBuilder();
            while (idx < s.length() && s.charAt(idx) != ']') {
                char c = s.charAt(idx);
                if (c == ' ') {
                    idx++;
                    continue;
                }

                if (c >= '0' && c <= '9') {
                    cur = cur * 10 + (c - '0');
                    idx++;
                } else if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
                    sb.append(c + "");
                    idx++;
                } else { //遇到[ 了
                    Info info = f(s, idx + 1);
                    sb.append(getRestr(info.data, cur));
                    cur = 0;
                    idx = info.idx + 1;
                }
            }
            return new Info(sb.toString(), idx);
        }

        public String getRestr(String s, int repet) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < repet; i++) {
                sb.append(s);
            }

            return sb.toString();
        }

        static class Info {
            String data;
            int idx;

            public Info(String s, int i) {
                data = s;
                idx = i;
            }
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.expressionExpand("abc3[a]").equals("abcaaa"));
        System.out.println(obj.expressionExpand("3[2[ad]3[pf]]xyz").equals("adadpfpfpfadadpfpfpfadadpfpfpfxyz"));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有194条未读消息，请及时查看
575 · 字符串解码
算法
中等
通过率
41%

题目
题解59
笔记
讨论99+
排名
记录
描述
给出一个表达式 s，此表达式包括数字，字母以及方括号。在方括号前的数字表示方括号内容的重复次数(括号内的内容可以是字符串或另一个表达式)，请将这个表达式展开成一个字符串。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


数字只能出现在“[]”前面。

样例
样例1

输入: S = abc3[a]
输出: "abcaaa"
样例2

输入: S = 3[2[ad]3[pf]]xyz
输出: "adadpfpfpfadadpfpfpfadadpfpfpfxyz"
挑战
你可以不通过递归的方式完成展开吗？

相关知识
学习《2024年6月北美大厂最新面试真题精讲》课程中的3.1Bytedance：最新面试精选001相关内容 ，了解更多相关知识！
标签
企业
雅虎
Yelp
Coupang
Facebook
相关题目

367
表达树构造
困难

368
表达式求值
困难

885
字符串的最短长度编码
困难
推荐课程

系统设计 System Design 2024版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
